'''
Normalize-对参数化序列实行规范化
Distance-求两点间距离
InitK-确定福利参数化的修正系数k
InitU-对数据点实行参数化
'''

# 规范化
def Normalize(U:[float]):
    for i in range(len(U)):
        U[i] = U[i]/U[-1]

# 两点距离
def Distance(P1:[float], P2:[float]):
    n1 = len(P1)
    n2 = len(P2)
    if n1!=n2:
        return
    s = 0
    for i in range(n1):
        s += (P1[i]-P2[i])**2
    return s**0.5

# 初始化修正系数
import math
def InitK(Pts):
    n = len(Pts)
    D1 = [Distance(Pts[i-1], Pts[i]) for i in range(1,n)]
    D2 = [Distance(Pts[i-1], Pts[i+1]) for i in range(1,n-1)]
    # 计算弦线夹角的外角
    sita = [0.0]*n
    for i in range(n-2):
        d1 = D1[i]; d2 = D1[i+1]; d3 = D2[i]
        # 余弦公式
        th = math.acos((d1*d1+d2*d2-d3*d3)/(2*d1*d2))
        Pi = math.pi
        sita[i+1] = Pi-th if (Pi-th)<(Pi/2) else Pi/2
    # 计算修正系数
    k = [0.0]*n
    for i in range(1, n):
        t1 = 0 if i==1 else D1[i-2]
        t3 = 0 if i==n-1 else D1[i]
        t2 = D1[i-1]
        k[i] = 1+1.5*((t1*sita[i-1])/(t1+t2)+(t3*sita[i])/(t2+t3))
    return k

# 对数据点实现参数化
def InitU(Pts:[[float],[float],...], type:int):
    '''
        功能：对数据点实现参数化
        输入参数：Pts-数据点; type-参数化类型。
        输出参数：U-数据点参数值数组。
    '''
    n = len(Pts)
    U = [0.0]*n
    if type==0: # 规范均匀参数化
        U = list(range(n))
    elif type==1: #规范弦长参数化
        for i in range(1,n):
            U[i] = Distance(Pts[i-1],Pts[i]) + U[i-1]
    elif type==2: #规范向心参数化
        for i in range(1,n):
            U[i] = (Distance(Pts[i-1],Pts[i]))**0.5 + U[i-1]
    elif type==3: #规范福利参数化
        k = InitK(Pts)
        for i in range(1,n):
            U[i] = k[i]*Distance(Pts[i-1],Pts[i]) + U[i-1]
    Normalize(U)
    return U

if __name__ == '__main__':
    Pts = [(1,2,3),(4,3,5),(4,-2,4),(9,3,2)]
    print(InitU(Pts, 3))